#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<fstream>
#define NULL 0
unsigned int key;
unsigned int key1;
unsigned int key2;
int *p;
struct node //建节点
{
	char name[8],address[20];
	char num[11];
	node *next;
};
typedef node *pnode;
typedef node *mingzi;
node **phone;
node **nam;
node *a;
using namespace std;//使用名称空间
hash(char num[11])//建表，以人的电话号码为关键字，建立相应的散列表//若哈希地址发生冲突，进行冲突处理。
{
	int i=3,j;
	key1=(int)num[2];
	while(num[i]!=NULL)
	{
		key1+=(int)num[i];
			i++;
		}
		key1=key1%20;
		for(j=0;j<20;j++)//线性探测法解决冲突
		{
			key=(key1+j)%20;
			if(phone[key]->num==" ")
				break;
		}
		return(key);
	}
	hash2(char name[8]) //建表，以人的姓名为关键字，建立相应的散列表//若哈希地址发生冲突，进行冲突处理
	{
		int i=1,j;
		key2=(int)name[0];
		while(name[i]!=NULL)
		{
			key2+=(int)name[i];
			i++;
		}
		key2=key2%20;
		for(j=0;j<20;j++)//线性探测法解决冲突
		{
			key=(key2+j)%20;
			if(phone[key]->name=="")
				break;
		}
		return(key);
	}
	node *input() //输入节点
	{
		node *temp;
		temp = new node;
		temp->next=NULL;
		cout<<"输入姓名："<<endl;
		cin>>temp->name;
		cout<<"输入地址："<<endl;
		cin>>temp->address;
		cout<<"输入电话："<<endl;
		cin>>temp->num;
		return temp;
	}
	int apend() //添加节点
	{
		node *newphone;
		node *newname;
		newphone=input();
		newname=newphone;
		newphone->next=NULL;
		newname->next=NULL;
		newphone->next=phone[hash(newphone->num)]->next;
		phone[hash(newphone->num)]->next=newphone;
		newname->next=nam[hash2(newname->name)]->next;
		nam[hash2(newname->name)]->next=newname;
		return 0;
	}
	void create() //新建电话号码数组
	{
		int i;
		phone=new node[20];
		for(i=0;i<20;i++)
		{
			phone[i]=new node;
			phone[i]->next=NULL;
		}
	}
	void create2() //新建姓名数组
	{
		int i;
		nam=new mingzi[20];
		for(i=0;i<20;i++)
		{
			nam[i]=new node;
			nam[i]->next=NULL;
		}
	}
	void list()//显示列表（号码散列）
	{
		int i;
		node *p;
		for(i=0;i<20;i++)
		{
			p=phone[i]->next;
			while(p)
			{
				cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;
				p=p->next;
			}
		}
	}
	void list2()//显示列表（姓名散列）
	{
		int i;
		node *p;
		for(i=0;i<20;i++)
		{
			p=nam[i]->next;
			while(p)
			{
				cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;
				p=p->next;
			}
		}
	}
	void find(char num[11])//查找用户信息（号码查找）
	{
		int i,j=0;
		node *p;
		for(i=0;i<20;i++)
		{
			p=phone[i]->next;
			while(p)
			{
				if(strcmp(num,p->num)==0)
				{
					cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;
					j++;
				}
				p=p->next;
			}
		}
		if(j==0)
			cout<<"无此记录"<<endl;
	}
	void find2(char name[8]) //查找用户信息（姓名查找）
	{
		int i,j=0;
		node *p;
		for(i=0;i<20;i++)
		{
			p=nam[i]->next;
			while(p)
			{
				if(strcmp(name,p->name)==0)
				{
					cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;
					j++;
				}
				p=p->next;
			}
		}
		if(j==0)
			cout<<"无此记录"<<endl;
	}
	void Delete(char num[11])
	{
		node *P;
		hash(num);
		p=phone[key]->next;
		phone[key]->next=p->next;
	}
	void Delete1(char name[8])
	{
		node *p;
		hash2(name);
		p=nam[key]->next;
		nam[key]->next=p->next;
	}
	void save()//保存用户信息
	{
		int i;
		node *p;
		fstream iiout("out.txt",ios::out);
		for(i=0;i<20;i++)
		{
			p=phone[i]->next;
			while(p)
			{
				iiout<<p->name<<"_"<<p->address<<"_"<<p->num<<endl;
				p=p->next;
			}
		}
	}
	void menu() //菜单
	{
		cout<<"______________"<<endl;
		cout<<"|0.添加记录|"<<endl;
		cout<<"|1.查找记录|"<<endl;
		cout<<"|2.姓名散列|"<<endl;
		cout<<"|3.号码散列|"<<endl;
		cout<<"|4.清空记录|"<<endl;
		cout<<"|5.保存记录|"<<endl;
		cout<<"|6.删除信息|"<<endl;
		cout<<"|7.退出系统|"<<endl;
		cout<<"______________"<<endl;
	}
	int main()
	{
		cout<<"欢迎使用电话号码查找系统"<<endl;
		cout<<"************************"<<endl;
		char num[11];
		char name[8];
		create();
		create2();
		int sel;
		while(1)
		{
			menu();
			cout<<"请输入要选择的操作："<<endl;
			cin>>sel;//输入选择项目操作
			if(sel==0)
			{
				cout<<"请输入要添加的内容："<<endl;
				apend();
			}
			else if(sel==1)
			{
				cout<<"9号码查询，8姓名查询"<<endl;
				int b;
				cin>>b;
				if(b==9)
				{
					cout<<"请输入电话号码："<<endl;
					cin>>num;
					cout<<"请输入查找的信息："<<endl;
					find(num);
				}
				else if(b==8)
				{
					cout<<"请输入姓名："<<endl;
					cin>>name;
					cout<<"请输入查找的信息："<<endl;
					find2(name);
				}
				else printf("不合法操作~\n");
			}
			else if(sel==2)
			{
				cout<<"姓名散列的结果："<<endl;
				list2();
			}
			else if(sel==3)
			{
				cout<<"号码散列结果："<<endl;
				list();
			}
			else if(sel==4)
			{
				cout<<"列表已清空："<<endl;
				create();
				create2();
			}
			else if(sel==5)
			{
				cout<<"通信录已保存："<<endl;
				save();
			}
			else if(sel==6)
			{
				int c;
				cout<<"删除信息："<<endl;
				cout<<"9.按号码删除8.按姓名删除"<<endl;
				cin>>c;
				if(c==9)
				{
					cout<<"请输入号码："<<endl;
					cin>>num;
					Delete(num);
				}
				else if(c==8)
				{
					cout<<"请输入姓名："<<endl;
					cin>>name;
					Delete1(name);
				}
				else cout<<"不合法操作~"<<endl;
				cout<<"信息已删除\n"<<endl;
			}
			else if(sel==7)
				return 0;
			else cout<<"不合法操作~"<<endl;
		}
		return 0;
	}


